package com.mj.listen1._15_补充._二叉树的非递归遍历.tree;

import com.mj.listen1._15_补充._二叉树的非递归遍历.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    // 根节点
    protected Node<E> root;

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空所有元素
    public void clear() {
        root = null;
        size = 0;
    }

    /**********      遍历      **********/
    // 前序遍历
    public void preorderTraversal(Visitor<E> visitor) {
        this.preorderTraversal(root, visitor);
    }

    private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }

        if (visitor.stop) return;
        // 先访问父节点
        visitor.stop = visitor.visit(node.element);// 打印节点
        // 再访问左边
        preorderTraversal(node.left, visitor);
        // 最后右边
        preorderTraversal(node.right, visitor);
    }

    // 中序遍历
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        this.inorderTraversal(root, visitor);
    }

    private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }

        // 先访问左边
        inorderTraversal(node.left, visitor);
        if (visitor.stop) return;
        // 再中间访问父节点
        visitor.stop = visitor.visit(node.element);
        // 最后访问右边
        inorderTraversal(node.right, visitor);
    }

    // 后序遍历
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        this.postorderTraversal(root, visitor);
    }

    private void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) {
            return;
        }

        // 先访问左边
        postorderTraversal(node.left, visitor);
        // 再中间访问右边
        postorderTraversal(node.right, visitor);
        // 最后访问父节点
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    // 层序遍历
    public void levelOrderTranversal(Visitor<E> visitor) {
        if (visitor == null) return;
        if (root == null) {
            return;
        }
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            // 取出根节点输出
            node = queue.poll();
            // 打印节点
            if (visitor.visit(node.element)) return;

            // 添加左孩子到队列中
            if (node.left != null) {
                queue.offer(node.left);
            }

            // 添加右孩子到队列中
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**********      遍历      **********/

    // 获取二叉搜索树的高度，其实就是根节点的高度
    public int height2() {
        // 通过递归的方式
        return height(root);
    }

    // 获取node节点的高度
    private int height(Node<E> node) {
        if (node == null) return 0;
        // 递归。节点的高度 = 1 + 左右孩子节点的高度的最大值
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // 获取二叉搜索树的高度。非递归，遍历的方式。
    // 借用层序遍历
    public int height() {
        if (root == null) {
            return 0;
        }
        // 记录高度
        int height = 0;
        // 记录每一层的个数，默认就是1个
        int levelSize = 1;
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            // 取出根节点输出
            node = queue.poll();
            levelSize--;

            // 添加左孩子到队列中
            if (node.left != null) {
                queue.offer(node.left);
            }

            // 添加右孩子到队列中
            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) {
                // 说明换行了，记录下一行的数量，下一行的数量。恰好是队列的大小
                levelSize = queue.size();
                height++;// 换行了
            }
        }
        return height;
    }

    // 判断二叉树是否是完全二叉树
    public boolean isCompleteTree2() {
        if (root == null) {
            return false;
        }
        // 后续的节点必须是叶子节点
        boolean mastIsLeaf = false;
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();

            // 必须是叶子节点，但是当前遍历到的节点不是叶子节点，那么久不是完全二叉树
            if (mastIsLeaf && !node.isLeaf()) {
                return false;
            }

            if (node.hasTwoChildren()) {
                // 孩子节点入队
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                // 没有左孩子，有右孩子
                return false;
            } else {
                // 此时后续的节点必须都是叶子节点
                mastIsLeaf = true;
                // 后面遍历的节点全部为叶子节点，才是完全二叉树
                if (node.left != null) {// 7 4 9 2 1不加这行代码会报错
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }

    // 判断二叉树是否是完全二叉树 最终版
    public boolean isCompleteTree() {
        if (root == null) {
            return false;
        }
        // 后续的节点必须是叶子节点
        boolean mastIsLeaf = false;
        Node<E> node = root;
        Queue<Node<E>> queue = new LinkedList<>();
        // 往队列填充根节点
        queue.offer(node);

        while (!queue.isEmpty()) {
            node = queue.poll();

            if (mastIsLeaf && !node.isLeaf()) {
                return false;
            }

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {// node.left == null
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else {// node.right == null
                // node.left == null || node.left != null
                mastIsLeaf = true;
            }
        }
        return true;
    }

    /**
     * 根据传入的节点, 返回该节点的前驱节点 (中序遍历)
     *
     * @param node
     * @return
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        Node<E> p = node.left;
        // 左子树不为空
        if (p != null) {
            // left.right
            while (p.right != null) {
                p = p.right;
            }
            // 左子树的底部最右侧的节点
            return p;
        }

        // 左子树为空
        // 去找parent，parent不为空，node在parent的左子树中，继续往上找parent
        if (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // left == null && node.parent == null。返回null
        return node.parent;
    }

    /**
     * 根据传入的节点, 返回该节点的后驱节点 (中序遍历)
     *
     * @param node
     * @return
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return node;

        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // node.right为空
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }

    protected Node<E> createNode(E element, Node<E> parent) {
        return new Node<>(element, parent);
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node<E>) node).element;
    }

    /**
     * 前序遍历非递归实现，另一种思路
     *
     * @param visitor
     */
    public void preorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> pop = stack.pop();
            // 访问节点
            if (visitor.visit(pop.element)) return;
            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }


    /**
     * 前序遍历非递归实现
     *
     * @param visitor
     */
    public void preorder2(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        while (true) {
            if (null != node) {
                // 访问节点
                if (visitor.visit(node.element)) return;
                // 存储访问节点的右子节点
                if (node.right != null) {
                    stack.push(node.right);
                }
                // 向左走
                node = node.left;
            } else {
                if (stack.isEmpty()) {
                    // 一路向左找，左节点为空，且栈没有节点，结束
                    return;
                }
                // 一路向左找，左节点为空，栈中还有节点了，从栈中取出来
                node = stack.pop();
            }
        }
    }

    /**
     * 中序遍历非递归实现
     *
     * @param visitor
     */
    public void inorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
//        while (true) {
//            if (node != null) {
//                // 访问到的节点入栈
//                stack.push(node);
//                // 一路向左找。
//                node = node.left;
//            } else if (stack.isEmpty()) {
//                // 栈为空了，说明已经遍历到了最后一个
//                return;
//            } else {
//                // 取出栈顶的节点
//                Node<E> pop = stack.pop();
//                // 访问节点
//                if (visitor.visit(pop.element)) return;
//                if (pop.right != null) {
//                    // 该父节点有右子节点，从右子节点开始执行前面入栈操作
//                    node = pop.right;
//                }
//            }
//        }
        while (true) {
            if (node != null) {
                // 访问到的节点入栈
                stack.push(node);
                // 一路向左找。
                node = node.left;
            } else {
                if (stack.isEmpty()) {
                    return;
                }
                // 取出栈顶的节点
                node = stack.pop();
                // 访问节点
                if (visitor.visit(node.element)) return;
                // 看是否有右子节点。如果没有的话，会继续执行else里面的代码，弹出上一层的中间节点；如果有的话，右继续从右子节点开始执行前面入栈操作
                node = node.right;
            }
        }
    }

    /**
     * 后序遍历非递归实现
     *
     * @param visitor
     */
    public void postorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        // 记录上一个弹出的节点
        Node<E> preNode = null;
        while (!stack.isEmpty()) {
            Node<E> peek = stack.peek();
            // peek.isLeaf() :peek.left == null && peek.right == null
            // preNode == peek.left || preNode == peek.right: (preNode != null && peek == preNode.parent)
            if ((peek.left == null && peek.right == null) || (preNode == peek.left || preNode == peek.right)) {
                preNode = stack.pop();
                // 访问节点
                if (visitor.visit(preNode.element)) return;
            } else {
                if (peek.right != null) {
                    stack.push(peek.right);
                }

                if (peek.left != null) {
                    stack.push(peek.left);
                }
            }
        }
    }

    protected static class Node<E> {
        public Node<E> left;
        public Node<E> right;
        public Node<E> parent;
        public E element;

        /**
         * 是否是叶子
         *
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 当前节点是否有两个孩子
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        // 这里不初始化左,右结点,因为不常用,比如所叶子结点,就没有左右结点
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断自己是否是左孩子
         *
         * @return
         */
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 判断自己是否是右孩子
         *
         * @return
         */
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        /**
         * 获取兄弟节点。获取叔父节点：parent.isSibling();
         *
         * @return
         */
        public Node<E> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }

            if (isRightChild()) {
                return parent.left;
            }

            return null;
        }
    }

    public static abstract class Visitor<E> {
        boolean stop;

        /**
         * @return 如果返回true，就代表停止遍历
         */
        public abstract boolean visit(E element);
    }

}
